/**
 * 由于本工程为C语言开发环境，此代码使用cpp语法，故仅做汇总。
 * 运行调试使用Cpp_training工程。
 */


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
// 定义一个动态数组
typedef struct SSTable {
    ElemType *elem;
    int length;
};

// 数组初始化
void ST_Init(SSTable &ST, int length) {
    ST.length = length;
    ST.elem = (ElemType*) malloc(sizeof (ElemType)*length);
    // 生成一个随机序列
    srand(time(NULL));  // 初始化随机种子，使得后面的rand()函数生成随机数
    for (int i = 0; i < ST.length; ++i) {
        ST.elem[i] = rand()%100;
    }
}

// 数组打印
void ST_Print(SSTable ST) {
    for (int i = 0; i < ST.length; ++i) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}

// 数组交换元素顺序
void swap(ElemType &a, ElemType &b) {
    ElemType tmp = a;
    a = b;
    b = tmp;
}

/**
 * 冒泡排序
 * 每次把未排序的元素中最小的元素排列到最前面
 * @param ST
 */
void BubbleSort(SSTable &ST) {
    for (int i = 0; i < ST.length; i++) {
        bool flag = true;
        for (int j = ST.length-1; j > i; j--) {
            if (ST.elem[j-1] > ST.elem[j]) {
                swap(ST.elem[j - 1], ST.elem[j]);
                flag = false;
            }
        }
        // 如果没有移动元素，证明序列已经有序，直接结束
        if (flag) {
            return;
        }
    }
}

/**
 * 快速排序
 * 确定一个元素作为枢轴（分割点），遍历所有元素，所有小于轴的元素放在左侧，大于轴的放在右侧
 * @param ST
 * @param low
 * @param high
 * @return
 */
// 快排分割
int Partition(SSTable &ST, int low, int high) {
    int i;          // 用来遍历需要排列的元素
    int k;          // 用来标记要交换的分割点的位置
    for (i = low, k = low; i < high; ++i) {
        if (ST.elem[i] < ST.elem[high]) {
            swap(ST.elem[i], ST.elem[k]);
            k++;
        }
    }
    // 其他元素比较完成后，最右侧的元素移动到分割点的位置
    swap(ST.elem[k], ST.elem[high]);
    return k;
}

// 快速排序
void QuickSort(SSTable &ST, int low, int high) {
    if (low < high) {
        int pivotPos = Partition(ST, low, high);
        QuickSort(ST, low, pivotPos-1);
        QuickSort(ST, pivotPos+1, high);
    }
}

/**
 * 插入排序
 * 将无序数依次插入有序序列。遍历过的部分是有序序列，后面是无序数。
 * @param ST
 */
// 插入排序
void InsertSort(SSTable &ST) {
    // 新建一个比原数组多一位的辅助序列，辅助序列第一位元素当作哨兵
    SSTable ST_assist;
    ST_Init(ST_assist, ST.length+1);
    ST_assist.elem[0] = 0;
    for (int i = 0; i < ST.length; ++i) {
        ST_assist.elem[i+1] = ST.elem[i];
    }
    // 排序，从原数组的第二个元素开始排列
    // 原数组元素所在位置对应辅助数组中的下标
    for (int i = 2; i <= ST.length; ++i) {
        ST_assist.elem[0] = ST_assist.elem[i];
        for (int j = i; j > 0; --j) {
            if (ST_assist.elem[j-1] <= ST_assist.elem[0]) {
                ST_assist.elem[j] = ST_assist.elem[0];
                break;
            }
            ST_assist.elem[j] = ST_assist.elem[j-1];
        }
    }
    // 赋值给原数组
    for (int i = 0; i < ST.length; ++i) {
        ST.elem[i] = ST_assist.elem[i+1];
    }
}

/**
 * 读取10个整型数据12 63 58 95 41 35 65  0 38 44，然后通过冒泡排序，快速排序，插入排序，分别对该组数据进行排序，输出3次有序结果，每个数的输出占3个空格
 * @return
 */
int main() {
    SSTable ST, ST_bubble, ST_quick, ST_insert;
    ElemType A[10] = {12, 63, 58, 95, 41, 35, 65, 0, 38, 44};
    // 初始化数组
    ST_Init(ST, 10);
    ST_Init(ST_bubble, 10);
    ST_Init(ST_quick, 10);
    ST_Init(ST_insert, 10);
    // 拷贝整型数组或浮点型数组时，用memcpy。拷贝字符串数组时，用strcpy
    memcpy(ST.elem, A, sizeof (A));             // 将数组A中的元素复制到ST.elem中
    memcpy(ST_bubble.elem, ST.elem, sizeof (ElemType)*ST.length);
    memcpy(ST_quick.elem, ST.elem, sizeof (ElemType)*ST.length);
    memcpy(ST_insert.elem, ST.elem, sizeof (ElemType)*ST.length);
//    ST_Print(ST);

    // 实现从小到大排序
    // 冒泡排序
    BubbleSort(ST_bubble);
    ST_Print(ST_bubble);
    // 快速排序
    QuickSort(ST_quick, 0, ST.length-1);
    ST_Print(ST_quick);
    // 插入排序
    InsertSort(ST_insert);
    ST_Print(ST_insert);

    return 0;
}